459. 重复的子字符串

Similar Question

Solution Tips

方案一: 脑筋急转弯

var repeatedSubstringPattern = function (s) {
  // s = s.split('');
  // const data = [...new Set(s)];
  // return s.length % data.length === 0 && s.length !== data.length ? true : false;

  const str = s + s;
  return str.substring(1, str.length - 1).includes(s)
};

方案二: 富途二面 - 临时方案

function checkRepeat(s) {
    if (s.length === 0) return false;
    // 一定是由子串构成的
    // 上界: 最长的子串就是 s.length / 2, 重复一次构成
    // 可以暴力法 0 - half 所有长度的子串
    // 记录子串的 哈希表, s 的哈希表, s 的哈希表一定是 子串的 n 倍
    // s 的哈希表中所有的字母

    // 子串重复 n / sn 次
    const map = {};
    for (let i = 0; i < s.length; i++) {
        map[s[i]] = (map[s[i]] || 0) + 1;
    }

    // 奇偶数长度是否有影响? 一个奇数的有可能是重复构成的么? aaa abcabcabc, floor
    const half = Math.floor(s.length / 2);
    const subMap = {};
    for (let i = 0; i < half; i++) {
        // 从 0 到 i 的子串能否构成 s
        subMap[s[i]] = (subMap[s[i]] || 0) + 1;

        // 判断两个map的关系
        const time = canRepeat(map, subMap)
        if (time) {
            if (s.slice(0, i + 1).repeat(time) === s) {
                return true;
            }
        }
    }

    return false;

    function canRepeat(map, subMap) {
        let multiple;
        for (const [key, val] of Object.entries(map)) {
            const subCount = subMap[key];
            if (!multiple) {
                multiple = (val / subCount);
            }
            else if (multiple !== (val / subCount)) {
                return false;
            }
        }

        return multiple;
    }
}

function checkRepeat2(s) {

    if (s.length === 0) return false;

    const half = Math.floor(s.length / 2);
    for (let i = 0; i < half; i++) {
        const sub = s.slice(0, i + 1);
        // console.log('sub: ', sub);

        // console.log('s.length % sub.length: ', s.length % sub.length);
        // console.log('s.length / sub.length: ', s.length / sub.length);
        if (s.length % sub.length === 0) {
            if (sub.repeat(s.length / sub.length) === s) {
                return true;
            }
        }
    }

    return false;
}

// 补充单测, 基于测试用例完善, 考虑边界情况
// console.log(checkRepeat(''));
// console.log(checkRepeat('12312356'));
// console.log(checkRepeat('ababab'));
// console.log(checkRepeat('abcab'));
// console.log(checkRepeat('aaaa'));
// console.log(checkRepeat('abcabcabc'));
// console.log(checkRepeat('abba'));
// console.log(checkRepeat('aabaab'));

console.log(checkRepeat2(''));
console.log(checkRepeat2('12312356'));
console.log(checkRepeat2('ababab'));
console.log(checkRepeat2('abcab'));
console.log(checkRepeat2('aaaa'));
console.log(checkRepeat2('abcabcabc'));
console.log(checkRepeat2('abba'));
console.log(checkRepeat2('aabaab'));
console.log(checkRepeat2('abcabc'));